#include <iostream>
#include <queue>
#include <vector>

using namespace std;
class Solution
{
 public:
  int get_single_sum(int x)
  {
    int s = 0;
    while (x) s += x % 10, x /= 10;
    return s;
  }

  int get_sum(pair<int, int> p) { return get_single_sum(p.first) + get_single_sum(p.second); }

  int movingCount(int threshold, int rows, int cols)
  {
    int res;
    if (!rows || !cols) return 0;

    vector<vector<bool>> st(rows, vector<bool>(cols));
    queue<pair<int, int>> q;

    q.push({0, 0});

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while (q.size())
    {
      auto t = q.front();
      q.pop();

      if (get_sum(t) > threshold || st[t.first][t.second]) continue;
      res++;
      st[t.first][t.second] = true;

      for (int i = 0; i < 4; i++)
      {
        int x = t.first + dx[i], y = t.second + dy[i];
        if (x >= 0 && x < rows && y >= 0 && y < cols)
        {
          q.push({x, y});
        }
      }
    }

    return res;
  }
};
